package baseclass.f_hash;

/**
 * 一个矩阵中只有0和1两种值， 每个位置都可以和自己的上、 下、 左、 右
 * 四个位置相连， 如果有一片1连在一起， 这个部分叫做一个岛， 求一个
 * 矩阵中有多少个岛？
 * 举例：
 * 0 0 1 0 1 0
 * 1 1 1 0 1 0
 * 1 0 0 1 0 0
 * 0 0 0 0 0 0
 * 这个矩阵中有三个岛
 * <p>
 * 分析：方式1：依次遍历矩阵，当有元素是1的时候，进行感染操作，把能够感染到的数都置成2.
 * 已经被感染过的当遍历再遇见的时候由于不是1会直接跳。
 * 感染的过程：以当前点为中心，进行上下左右传播。
 * 更多解法见{@link leetcode.top100.Code200_NumLands_岛屿数量}
 */
public class Code04_IsLands {
    public static int countIsLands(int[][] map) {
        if (map == null || map[0] == null) {
            return 0;
        }
        int row = map.length;
        int col = map[0].length;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] == 1) {
                    count++;
                    infect(map, i, j, row, col);
                }
            }
        }
        //TODO 遍历把2修改为1
        return count;
    }

    private static void infect(int[][] map, int i, int j, int row, int col) {
        if (i < 0 || i >= row || j < 0 || j >= col // 越界
                ||
                map[i][j] != 1) {//不符合感染条件
            return;
        }
        //否则先把感染过的变为2
        map[i][j] = 2;
        //再递归感染前后左右
        infect(map, i, j - 1, row, col);//左
        infect(map, i, j + 1, row, col);//右
        infect(map, i - 1, j, row, col);//上
        infect(map, i + 1, j, row, col);//下

    }

    public static void main(String[] args) {
        int[][] m1 = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},};
        System.out.println(countIsLands(m1));

        int[][] m2 = {{0, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 1, 1, 1, 1, 1, 1, 0},
                {0, 1, 1, 1, 0, 0, 0, 1, 0},
                {0, 1, 1, 0, 0, 0, 1, 1, 0},
                {0, 0, 0, 0, 0, 1, 1, 0, 0},
                {0, 0, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0},};
        System.out.println(countIsLands(m2));

    }
}
